package com.cjm.algorithm.backtracking;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class Ti3920240603 {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        // 候选的长度
        int len = candidates.length;
        // 答案容器
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        // 如果没有元素，还算个什么东西哦
        if (len == 0) return res;
        // 一个path，用于记录我们一路的历程
        Deque<Integer> path = new ArrayDeque<Integer>();
        // 开始回溯了
        dfs(candidates, 0, len, target, path, res);
        // 返回答案
        return res;
    }

    // 这道的意思， 就是一个元素， 可以重复使用
    // 这里的意思，就是逐渐的将target减少
    private void dfs(int[] candidates, int begin, int len, int target,
                     Deque<Integer> path, List<List<Integer>> res) {
        // 当减少后的值已经小于0了， 那么就是减多了呗
        if (target < 0) {
            return;
        }
        // 如果等于0， 正好
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i = begin; i < len; i++) {
            path.addLast(candidates[i]);
            // 因为是可以重复使用的， 所以这里的i不变， 让他自己在for循环里自已增长吧
            dfs(candidates, i, len, target - candidates[i], path, res);
            path.removeLast();
        }
    }
}
